/**
 * Turn strings into keywords.
 * Call the public static method makeKeyword(String) to do that.
 * It removes stopwords, and it stems.  Based on the standard Porter stemmer.
 * Modified to use char arrays instead of Strings for speed by Paul Kube.
 * @author Paul Kube
 * @author Fotis Lazarinis
 */
public class Keyword {

  /**
   * Turn a String into a keyword.
   * @param w The word to keywordize.
   * @return the stemmed keyword.  Will return the empty string
   * if w is a stopword or otherwise not a valid keyword.
   */
  public static String makeKeyword(String w) {
    w = w.toLowerCase();
    if ( isStop(w) ) return "";
    else return stem(w);

  }
  

  /**
   * Say whether a word is a stop word.
   * @param w The word to check.
   * @return true if it is a stopword, else false.
   */
  public static boolean isStop(String w) {
    return stopSet.contains(w);
  }

  /**
   * Stem a string.
   * Convert to lowercase, clean punctuation and the like,
   * and if more than 2 chars long, strip prefixes and suffixes.
   * @param str The String to stem.
   * @return The stemmed String.
   */
  public static String stem( String str ) {
    // turn the string into a char array, for efficiency
    char[] carr = new char[str.length()];
    int len = carr.length;
    str.getChars(0,len,carr,0);
    // lowercase it
    for(int i=0; i<len; i++) {
      carr[i] = Character.toLowerCase(carr[i]);
    }
    // clean it
    len = clean(carr,len);
    // strip prefixes
    if(len > 2) {
      len = stripPrefixes(carr,len);
      // strip suffixes
      if(len > 0)
	len = stripSuffixes(carr,len);
    }
    
    return new String(carr,0,len);

  } //stem


  // remove anything not a letter or digit from carr.
  // return new effective length of carr.
  private static int clean( char[] carr, int len ) {
    int last = len;
    int i=0,j=0;
    for ( i=0; i < last; i++ ) {
      if ( !Character.isLetterOrDigit( carr[i] )) {
        carr[i] = (char)-1;	// mark deleted char with (char)-1
        len--;
      }
    }

    if(last == len) return len; // nothing changed

    // get rid of sentinel -1's, compacting array to the left
    for(i=0,j=0;i<last;i++) {
      if (carr[i] == (char)-1) continue;
      carr[j++] = carr[i];
    }
    return len;
   
  } //clean
 

  // return true if str ends with sfx, and is longer than sfx,
  // according to effective slen
  private static boolean endsWith(char[] str, int len, char[] sfx) {
    int slen = sfx.length;
    if (slen > len) return false; // suffix too long
    for(int i=0;i<slen;i++) {
      if(str[len-slen+i] != sfx[i]) return false;
    }
    return true;
  }

  // return true if str ends with sfx, and is longer than sfx,
  // according to effective slen
  private static boolean endsWith(char[] str, int len, String sfx) {
    int slen = sfx.length();
    if (slen >= len) return false; // suffix too long.  Note use of >=
    for(int i=0;i<slen;i++) {
      if(str[len-slen+i] != sfx.charAt(i)) return false;
    }
    return true;
  
  }


  private static boolean vowel( char ch, char prev ) {
    switch ( ch ) {
      case 'a': case 'e': case 'i': case 'o': case 'u': 
        return true;
      case 'y': {

        switch ( prev ) {
          case 'a': case 'e': case 'i': case 'o': case 'u': 
            return false;

          default: 
            return true;
        }
      }
        
      default : 
        return false;
    }
  }


  // return something like the length of the stem,
  // not counting vowels
  private static int measure( char[] stem, int len ) {
    
    int i=0, count = 0;

    while ( i < len ) {
      for ( ; i < len ; i++ ) {
        if ( i > 0 ) {
          if ( vowel(stem[i],stem[i-1]) )
            break;
        }
        else {  
          if ( vowel(stem[i],'a') )
            break; 
        }
      }

      for ( i++ ; i < len ; i++ ) {
        if ( i > 0 ) {
          if ( !vowel(stem[i],stem[i-1]) )
            break;
        }
        else {  
          if ( !vowel(stem[i],'?') )
            break;
        }
      } 
      if ( i < len ) {
        count++;
        i++;
      }
    } //while
    
    return(count);
  }

  private static boolean containsVowel( char[] word, int len ) {

    if ( vowel(word[0],'a') )
      return true;

    for (int i=1 ; i < len; i++ ) {
      
      if ( vowel(word[i],word[i-1]))
        return true;
    }
        
    return false;
  }

private static boolean cvc( char[] str, int len ) {

  if ( len < 3 )
    return false;
    
  if ( (!vowel(str[len-1],str[len-2]) )
       && (str[len-1] != 'w') && (str[len-1] != 'x') && (str[len-1] != 'y')
       && (vowel(str[len-2],str[len-3])) ) {

    if (len == 3) {
      if (!vowel(str[0],'?')) 
        return true;
      else
        return false;
    }
    else {
      if (!vowel(str[len-3],str[len-4]) ) 
        return true; 
      else
        return false;
    } 
  }   
  
  return false;
}

// return the new effective length of str after
// performing first step of suffix removal/modification
private static int step1( char[] str, int len ) {
 
  // deal with trailing 's'
  if ( str[ len-1 ] == 's' ) {
    if ( (endsWith( str, len, "sses")) || (endsWith( str, len, "ies")) ){
      // remove trailing 'es'
      len -= 2;
    }
    else {
      if ( ( len == 1 ) ) {
        return 0;  // down to single 's', forget it!
      }
      if ( str[ len-2 ] != 's' ) {
        // remove trailing 's' if not part of a double s
        len -= 1;
      }
    }  
  }

  // remove trailing 'd' from 'eed'
  if ( endsWith( str, len, "eed" ) ) {
    if ( measure( str, len-3 ) > 0 ) {
      // remove trailing 'd'
      len -= 1;
    }
  }
  else {
    // remove trailing 'ed' or 'ing'
    if (  (endsWith( str, len, "ed") && containsVowel(str, len-2)) ||
          (endsWith( str, len, "ing") && containsVowel(str, len-3))) {
      if( str[len-1] == 'd' )  {
        len -= 2; 
      } else  {
        len -= 3; 
      }
      if ( len == 1 ) return len; // too short, forget it

      if ( endsWith( str,len,"at") || endsWith( str,len,"bl") || endsWith( str,len,"iz")) {
        // add final 'e' (we have removed at least 2 chars, so this fits)
        str[len] = 'e';
        len += 1;
      }
      else {
        // doubled final letter, not 'l' or 's' or 'z'
        if ( (str[len-1] == str[len-2]) 
               && (str[len-1] != 'l') && (str[len-1] != 's') && (str[len-1] != 'z') ) {
                     
          // remove final letter
          len -= 1;
        } else  if ( measure( str, len ) == 1 &&  cvc(str,len) ) {
          // add final 'e' (we have removed at least 2 chars, so this fits)
          str[len] = 'e';
          len += 1;
        }
      }
    }
  }

  // change trailing y to i
  if ( endsWith(str,len,"y") && containsVowel( str, len-1 ) ) {
      str[len-1] = 'i';
  }

  return len;  
}

private static int step2( char[] str, int len ) {
     
  for ( int index = 0 ; index < step2suffixes.length; index++ ) {
    if ( endsWith( str, len, step2suffixes[index][0] ) ) {
      int s0len = step2suffixes[index][0].length();
      if ( measure ( str, len-s0len ) > 0 ) {
        // replace suffix
        int s1len = step2suffixes[index][1].length();
        for (int i=0; i<s1len; i++) {
          str[len-s0len+i] = step2suffixes[index][1].charAt(i);
        }
        return len - s0len + s1len;
      }
    }
  }

  return len;
}

private static int step3( char[] str, int len ) {

  for ( int index = 0 ; index < step3suffixes.length; index++ ) {
    if ( endsWith( str, len, step3suffixes[index][0] ) ) {
      int s0len = step3suffixes[index][0].length();
      if ( measure ( str, len-s0len ) > 0 ) {
        // replace suffix
        int s1len = step3suffixes[index][1].length();
        for (int i=0; i<s1len; i++) {
          str[len-s0len+i] = step3suffixes[index][1].charAt(i);
        }
        return len - s0len + s1len;
      }
    }
  }

  return len;
}

private static int step4( char[] str, int len ) {
        
  for ( int index = 0 ; index < step4suffixes.length; index++ ) {
    if ( endsWith( str, len, step4suffixes[index] ) ) {
      int s0len = step4suffixes[index].length();
      if ( measure ( str, len-s0len ) > 1 ) {
        // remove suffix
        return len - s0len;
      }
    }
  }

  return len;
}

// remove trailing e, if any
// then remove one of trailing double l, if any
private static int step5( char[] str, int len ) {

  if ( str[len-1] == 'e' ) { 
    if ( measure(str,len) > 1 ) {/* measure(str)==measure(stem) if ends in vowel */
      len -= 1;
    }
    else
      if ( measure(str,len) == 1 && !cvc(str,len-1)) {
        len -= 1;
      }
  }
     
  if ( len == 1 )
    return len;
  
  if ( (str[len-1] == 'l') && (str[len-2] == 'l') && (measure(str,len) > 1) ) {
    len -= 1;
    
  } 
  return len;
}

// return true if pfx is prefix of str
private static boolean startsWith(char[] str, int len, char[] pfx) {
  int plen = pfx.length;
  if (plen > len) return false; // prefix too long
  for(int i=0;i<plen;i++) {
    if(str[i] != pfx[i]) return false;
  }
  return true;
  
}

// return true if pfx is prefix of str
private static boolean startsWith(char[] str, int len, String pfx) {
  int plen = pfx.length();
  if (plen > len) return false; // prefix too long
  for(int i=0;i<plen;i++) {
    if(str[i] != pfx.charAt(i)) return false;
  }
  return true;
  
}
  

// remove the first-occuring prefix in the prefix array
private static int stripPrefixes ( char[] str, int len) {
  int last = prefixes.length;
  for ( int i=0 ; i<last; i++ ) {
    if (startsWith( str, len, prefixes[i] ) ) {
      // get rid of this prefix
      int plen = prefixes[i].length();
      for(int j=plen;j<len;j++) {
        str[j-plen] = str[j];
      }
      return len-plen;
    }
  }
  return len;
}


private static int stripSuffixes( char[] str, int len ) {
  if ( len > 0 )
    len = step1( str, len );
  if ( len > 0 )
    len = step2( str, len );
  if ( len > 0 )
    len = step3( str, len );
  if ( len > 0 )
    len = step4( str, len );
  if ( len > 0 )
    len = step5( str, len );
 
  return len; 
}



private static String[] prefixes = {
  "kilo", "micro", "milli", "intra", "ultra", "mega", "nano", "pico", "pseudo"
};

private static String[][] step2suffixes = {
  { "ational", "ate" },
  { "tional",  "tion" },
  { "enci",    "ence" },
  { "anci",    "ance" },
  { "izer",    "ize" },
  { "iser",    "ize" },
  { "abli",    "able" },
  { "alli",    "al" },
  { "entli",   "ent" },
  { "eli",     "e" },
  { "ousli",   "ous" },
  { "ization", "ize" },
  { "isation", "ize" },
  { "ation",   "ate" },
  { "ator",    "ate" },
  { "alism",   "al" },
  { "iveness", "ive" },
  { "fulness", "ful" },
  { "ousness", "ous" },
  { "aliti",   "al" },
  { "iviti",   "ive" },
  { "biliti",  "ble" }};

private static  String[][] step3suffixes = {
  { "icate", "ic" },
  { "ative", "" },
  { "alize", "al" },
  { "alise", "al" },
  { "iciti", "ic" },
  { "ical",  "ic" },
  { "ful",   "" },
  { "ness",  "" }};


private static String[] step4suffixes = {
  "al", "ance", "ence", "er", "ic", "able", "ible", "ant", "ement", "ment",
  "ent", "sion", "tion", "ou", "ism", "ate", "iti", "ous", "ive", "ize", "ise"
};

  
  // Stopwords are Strings in this array.  We'll put them in
  // stopSet for fast lookup
  private static String stopWords[] = {
    "a",
    "all",
    "am",
    "an",
    "and",
    "another",
    "any",
    "are",
    "as",
    "at",
    "be",
    "been",
    "but",
    "by",
    "each",
    "either",
    "else",
    "etc",
    "every",
    "for",
    "go",
    "had",
    "has",
    "hasnt",
    "have",
    "if",
    "in",
    "is",
    "isnt",
    "it",
    "its",
    "may",
    "neither",
    "nor",
    "of",
    "on",
    "or",
    "so",
    "than",
    "that",
    "the",
    "their",
    "them",
    "then",
    "these",
    "thus",
    "to",
    "too",
    "un",
    "was",
    "were",
    "what",
    "with"
  };

  // an agressive stopword list
  private static String stopWordsComplete[] = {
    "a",
    "about",
    "above",
    "across",
    "after",
    "afterwards",
    "again",
    "against",
    "all",
    "almost",
    "alone",
    "along",
    "already",
    "also",
    "although",
    "always",
    "am",
    "among",
    "amongst",
    "amoungst",
    "amount",
    "an",
    "and",
    "another",
    "any",
    "anyhow",
    "anyone",
    "anything",
    "anyway",
    "anywhere",
    "are",
    "around",
    "as",
    "at",
    "back",
    "be",
    "became",
    "because",
    "become",
    "becomes",
    "becoming",
    "been",
    "before",
    "beforehand",
    "behind",
    "being",
    "below",
    "beside",
    "besides",
    "between",
    "beyond",
    "bill",
    "both",
    "bottom",
    "but",
    "by",
    "call",
    "can",
    "cannot",
    "cant",
    "co",
    "computer",
    "con",
    "could",
    "couldnt",
    "cry",
    "de",
    "describe",
    "detail",
    "do",
    "done",
    "down",
    "due",
    "during",
    "each",
    "eg",
    "eight",
    "either",
    "eleven",
    "else",
    "elsewhere",
    "empty",
    "enough",
    "etc",
    "even",
    "ever",
    "every",
    "everyone",
    "everything",
    "everywhere",
    "except",
    "few",
    "fifteen",
    "fify",
    "fill",
    "find",
    "fire",
    "first",
    "five",
    "for",
    "former",
    "formerly",
    "forty",
    "found",
    "four",
    "from",
    "front",
    "full",
    "further",
    "get",
    "give",
    "go",
    "had",
    "has",
    "hasnt",
    "have",
    "he",
    "hence",
    "her",
    "here",
    "hereafter",
    "hereby",
    "herein",
    "hereupon",
    "hers",
    "herself",
    "him",
    "himself",
    "his",
    "how",
    "however",
    "hundred",
    "i",
    "ie",
    "if",
    "in",
    "inc",
    "indeed",
    "interest",
    "into",
    "is",
    "it",
    "its",
    "itself",
    "keep",
    "last",
    "latter",
    "latterly",
    "least",
    "less",
    "ltd",
    "made",
    "many",
    "may",
    "me",
    "meanwhile",
    "might",
    "mill",
    "mine",
    "more",
    "moreover",
    "most",
    "mostly",
    "move",
    "much",
    "must",
    "my",
    "myself",
    "name",
    "namely",
    "neither",
    "never",
    "nevertheless",
    "next",
    "nine",
    "no",
    "nobody",
    "none",
    "noone",
    "nor",
    "not",
    "nothing",
    "now",
    "nowhere",
    "of",
    "off",
    "often",
    "on",
    "once",
    "one",
    "only",
    "onto",
    "or",
    "other",
    "others",
    "otherwise",
    "our",
    "ours",
    "ourselves",
    "out",
    "over",
    "own",
    "part",
    "per",
    "perhaps",
    "please",
    "put",
    "rather",
    "re",
    "same",
    "see",
    "seem",
    "seemed",
    "seeming",
    "seems",
    "serious",
    "several",
    "she",
    "should",
    "show",
    "side",
    "since",
    "sincere",
    "six",
    "sixty",
    "so",
    "some",
    "somehow",
    "someone",
    "something",
    "sometime",
    "sometimes",
    "somewhere",
    "still",
    "such",
    "system",
    "take",
    "ten",
    "than",
    "that",
    "the",
    "their",
    "them",
    "themselves",
    "then",
    "thence",
    "there",
    "thereafter",
    "thereby",
    "therefore",
    "therein",
    "thereupon",
    "these",
    "they",
    "thick",
    "thin",
    "third",
    "this",
    "those",
    "though",
    "three",
    "through",
    "throughout",
    "thru",
    "thus",
    "to",
    "together",
    "too",
    "top",
    "toward",
    "towards",
    "twelve",
    "twenty",
    "two",
    "un",
    "under",
    "until",
    "up",
    "upon",
    "us",
    "very",
    "via",
    "was",
    "we",
    "well",
    "were",
    "what",
    "whatever",
    "when",
    "whence",
    "whenever",
    "where",
    "whereafter",
    "whereas",
    "whereby",
    "wherein",
    "whereupon",
    "wherever",
    "whether",
    "which",
    "while",
    "whither",
    "who",
    "whoever",
    "whole",
    "whom",
    "whose",
    "why",
    "will",
    "with",
    "within",
    "without",
    "would",
    "yet",
    "you",
    "your",
    "yours",
    "yourself",
    "yourselves"
  };

  private static java.util.HashSet<String> stopSet;  // the hash of stopwords

  static {  // static initializer:  set up the stopword table
    stopSet = new java.util.HashSet<String>((int)(stopWords.length * 1.2), 1.0F);
    for(String w: stopWords) {
      stopSet.add(w);
    }
  }



} //class
